package com.jack.leetcode.eachproblem_2020;

import java.util.ArrayList;
import java.util.List;

public class 路径总和2 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public List<List<Integer>> pathSum(TreeNode root, int sum) {

        List<List<Integer>> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        dfs(result, new ArrayList<>(), root, sum);
        return result;
    }

    private void dfs(List<List<Integer>> result, List<Integer> tmp,
                     TreeNode root, int sum){
        if(root == null){
            return;
        }
        if(root.left == null && root.right == null){
            if(0 == sum){
                result.add(new ArrayList<>(tmp));
            }
            return;
        }
        tmp.add(root.val);
        dfs(result, tmp, root.left, sum - root.val);
        dfs(result, tmp, root.right, sum - root.val);
        tmp.remove(tmp.size() - 1);
    }
}
